# -*- coding: utf-8 -*-

"""剑指 Offer II 006. 排序数组中两个数字之和
给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。
假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

示例 1：
输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。

示例 2：
输入：numbers = [2,3,4], target = 6
输出：[0,2]

示例 3：
输入：numbers = [-1,0], target = -1
输出：[0,1]
 

提示：
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 递增顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案"""

class Solution:
    """方案1:
    有序数组，挨个遍历，target-numbers[i]=addv，在该有序数组中二分查找addv。
    提交之后排位较低。

    方案2：
    有序数组，双指针
    """
    def twoSum_binsearch(self, numbers, target: int):
        def binsearch_LT(i, j):
            if j-i == 1:
                if numbers[j] <= target:
                    return j
                else:
                    return i

            m = (i+j)//2
            if numbers[m] > target:
                i, j = i, m
            elif numbers[m] <= target:
                i, j = m, j
            # else:
            #     i, j = m, j
            return binsearch_LT(i, j)
        
        lasti = len(numbers)-1
        anchor = binsearch_LT(0, lasti)

        def binsearch_EQ(i, j):
            if j-i == 1:
                if numbers[j] == addv:
                    return j
                else:
                    return None

            m = (i+j)//2
            if numbers[m] > addv:
                i, j = i, m
            elif numbers[m] < addv:
                i, j = m, j
            else:
                if m == p:
                    if m > 0 and numbers[m-1] == addv:
                        return m-1
                    elif m < lasti and numbers[m+1] == addv:
                        return m+1
                    else:
                        None
                else:
                    return m
            return binsearch_EQ(i, j)
            
        p, addv = None, None
        for p in range(0, anchor+1):
            addv = target-numbers[p]
            addi = binsearch_EQ(0, lasti)
            if addi:
                break
        
        return [p, addi]
    
    def twoSum(self, numbers, target):
        head, tail = 0, len(numbers)-1
        while True:
            total = numbers[head]+numbers[tail]
            if total == target:
                break
            elif total > target:
                tail -= 1
            else:
                head += 1
                                                
        return [head, tail]

if __name__ == '__main__':
    so = Solution()
    print(so.twoSum([1,2,4,6,10], 8))
    print(so.twoSum([2,3,4], 6))
    print(so.twoSum([-1,0], -1))
